﻿#define _CRT_SECURE_NO_WARNINGS 1

//动态规划第二题
//02_斐波那契数列模型_三步问题_C++
//https://leetcode.cn/problems/three-steps-problem-lcci/description/

//动态规划解决
class Solution {
public:
    int waysToStep(int n)
    {
        //1.创建dp表
        vector<long long> dp(n + 1);

        //2.状态转移方程
        //dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        //处理边界
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;

        //3.初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        //4.填表
        for (int i = 4; i <= n; i++)
        {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
        }

        return dp[n];
    }
};

//滚动数组优化

class Solution {
public:
    int waysToStep(int n)
    {
        //滚动数组优化

        //处理边界
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;

        long long a = 1, b = 2, c = 4;
        long long d = 0;

        for (int i = 4; i <= n; i++)
        {
            d = (a + b + c) % 1000000007;
            a = b;
            b = c;
            c = d;
        }

        return d;
    }
};

//二次编写

class Solution {
public:
    int waysToStep(int n)
    {
        const int MOD = 1e9 + 7;
        //2.状态转移方程
        //dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        //处理边界
        if (n == 1 || n == 2)
            return n;
        if (n == 3)
            return 4;

        //1.创建dp表
        vector<int> dp(n + 1);
        //3.初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
        //4.填表
        for (int i = 4; i <= n; i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }

        return dp[n];
    }
};

//滚动数组的优化
class Solution {
public:
    int waysToStep(int n) {
        // 滚动数组优化
        const int MOD = 1e9 + 7;

        // 处理边界
        if (n == 1 || n == 2)
            return n;
        if (n == 3)
            return 4;

        int a = 1, b = 2, c = 4, d = 0;

        for (int i = 4; i <= n; i++) {
            d = ((a + b) % MOD + c) % MOD;
            a = b;
            b = c;
            c = d;
        }

        return d;
    }
};